﻿

using System;
using System.IO;
using System.Linq;

namespace Graph.Algorithm.Core
{
    /*
     1 蚂蚁只经过每个点一次
     2 蚂蚁知道城市之间的距离  倾向于最近城市
     3 蚂蚁释放弗洛蒙，距离相同时，走弗洛蒙浓度高的路径
     */

    /// <summary>
    /// 蚁群算法
    /// </summary>
    public class AntColonyService
    {

        public double alpha { get; set; } = 2;
        public double beta { get; set; } = 5;
        public double Q { get; set; } = 10;
        public double rho { get; set; } = 0.5;

        public int[] path;

        public int cityNum { get; set; }

        public static MatrixBuilder<double> matBuilder { get; set; } = Matrix<double>.Build;

        Matrix<double> matrixDistance;
        Matrix<double> matrixPheromon;
        //Matrix<double> matrixPosibles;

        public List<int> bestPath = new List<int>();

        public AntColonyService(IEnumerable<GraphEdge> edges)
        {
            var groups = edges.GroupBy(e => e.stVertexId);
            this.cityNum = groups.Count();
            matrixDistance = matBuilder.Dense(cityNum, cityNum);
            matrixPheromon = matBuilder.Dense(cityNum, cityNum);

            for (int i = 0; i < cityNum; i++)
            {
                for (int j = 0; j < cityNum; j++)
                {
                    matrixDistance[i, j] = i == j ? 0 : edges.At(i, j).weight;
                    matrixPheromon[i, j] = i == j ? 0 : 0.4;
                }
            }

            path = new int[cityNum];
            for (int i = 0; i < cityNum; i++)
            {
                path[i] = i;
            }
            bestPath = path.ToList();
        }

        public AntColonyService(Matrix<double> _matrixDistance)
        {
            matrixDistance = _matrixDistance;
            int cityNum = _matrixDistance.RowCount;
              
            matrixDistance = matBuilder.Dense(cityNum, cityNum);
            matrixPheromon = matBuilder.Dense(cityNum, cityNum);

            for (int i = 0; i < cityNum; i++)
            {
                for (int j = 0; j < cityNum; j++)
                { 
                    matrixPheromon[i, j] = i == j ? 0 : 0.4;
                }
            }
             
            path = new int[cityNum];
            for (int i = 0; i < cityNum; i++)
            {
                path[i] = i;
            }
            bestPath = path.ToList();

        }

        public void CreateAntGeneration(int numberOfGeneration)
        {
            for (int i = 0; i < numberOfGeneration; i++)
            {
                //Console.WriteLine($"Number of generation:{i + 1}");
                FindPath();
            }
        }

        public void FindPath()
        {
            var mainPath = path.ToList();
            var tempPath = new List<int>();
            var antNum = mainPath.Count;
            //Dictionary<int, double> probabilities = new Dictionary<int, double>();
            for (int z = 0; z < antNum; z++)
            {
                int stIndex = 0;
                while (mainPath.Count != 0)
                {

                    ChooseCity(ref stIndex, mainPath, tempPath);
                }
            }

            UpdatePheromon(tempPath.ToArray());

        }

        public int[] GetBestPath(int stIndex)
        {
            var mainPath = path.ToList();
            var tempPath = new List<int>() { stIndex };
            //Dictionary<int, double> probabilities = new Dictionary<int, double>();
            for (int z = 0; z < 1; z++)
            {
                while (mainPath.Count != 0)
                {
                    ChooseCity(ref stIndex, mainPath, tempPath);
                }
            }
            bestPath = tempPath;
            return tempPath.ToArray();
        }

        public void ChooseCity(ref int stIndex, List<int> mainPath, List<int> tempPath)
        {
            Dictionary<int, double> probabilities = new Dictionary<int, double>();
            mainPath.Remove(stIndex);
            if (mainPath.Count == 0) { tempPath.Add(stIndex);return; }
            foreach (var i in mainPath)
            {
                double sum = 0;
                foreach (var j in mainPath)
                {
                    var pher = Math.Pow(matrixPheromon[stIndex, j], alpha);
                    var dist = Math.Pow((1 / matrixDistance[stIndex, j]), beta);
                    sum += dist * pher;
                }

                double curDist = matrixDistance[stIndex, i];
                double curPher = matrixPheromon[stIndex, i];

                double Probability =
                    (Math.Pow((1 / curDist), beta) * Math.Pow(curPher, alpha)) / sum;
                Probability = 100 * Probability;
                probabilities.Add(i, Probability);
            }
            probabilities = probabilities.OrderBy(x => x.Value).ToDictionary(x => x.Key, x => x.Value);
            //stIndex = GetNextCity(probabilities);
            if (probabilities.Count != 0) stIndex = probabilities.OrderBy(p => p.Value).Last().Key;//完全按照概率进行
            tempPath.Add(stIndex);
        }

        public int GetNextCity(Dictionary<int, double> dict)
        {
            Random rnd = new Random();
            var moveProb = rnd.Next(1, 100);

            foreach (var pair in dict)
            {
                if (moveProb < pair.Value)
                {
                    return pair.Key;
                }
            }
            return 0;
        }

        /// <summary>
        /// 更新信息素浓度
        /// </summary>
        void UpdatePheromon(int[] paths)
        {
            double pathLen = PathLength(paths);
            double avgPheromon = Q / pathLen;//每条走过路径上增加的费洛蒙

            int count = matrixPheromon.RowCount;
            //费洛蒙增量矩阵
            Matrix<double> matrixPheromonDelta = matBuilder.Dense(count, count, 0);
            for (int i = 0; i < paths.Count() - 1; i++)
            {
                int stIndex = paths[i];
                int edIndex = paths[i + 1];
                matrixPheromonDelta[stIndex, edIndex] += avgPheromon;
            }
            //更新信息素浓度
            matrixPheromon = matrixPheromon.Multiply(1d - rho) + matrixPheromonDelta;
        }

        public double PathLength(int[] _paths)
        {
            double pathSum = 0;
            for (int i = 0; i < _paths.Length - 1; i++)
            {
                pathSum += matrixDistance[_paths[i], _paths[i + 1]];
            }
            return pathSum;
        }

    }
}
